
from os import pathsep
import base_fun as fun
import copy
import csv
import json

import matplotlib.colors as mcolors
import matplotlib.pyplot as plt  # 导入 Matplotlib 工具包
import networkx as nx  # 导入 NetworkX 工具包
import numpy as np
import pandas as pd
colors = list(dict(mcolors.BASE_COLORS, **mcolors.CSS4_COLORS).keys())
# from .import base_fun as fun


def show_path_by_id(path, cid, scid):
    # path=[1, 15230, 29, 15114, 5056, 5058, 4483, 14999] #[15404, 15405, 730, 731, 732, 733, 734, 446, 445, 444, 443, 442, 441, 440, 439, 438, 437, 436, 435, 434, 433, 432, 431, 430, 429, 428, 427, 426, 425, 424, 423, 422, 421, 420, 419, 418, 417, 416, 415, 414, 413, 412, 411, 410, 409, 408, 407, 406, 405, 404, 403, 402, 401, 14456, 15062, 6067, 15060, 15059, 15058, 15057, 15221, 15220, 15511, 15510, 15509, 15212, 15507, 15506, 15505, 15504, 11259, 15502, 15501, 15500, 921, 15498, 15497, 15496, 15495, 15494, 15493, 15492, 15114]
    points, roadLines, roadpoint = view_maps2(True)  # 读取地图
    d3 = []
    for id in range(len(path)):
        d3.append(points[path[id]])
    d4 = np.array(d3)
    # plt.ion()

    # for i in range(len(d4)):
    #     cid=i%3
    plt.plot(d4[:, 0], d4[:, 1], color=colors[cid],
             marker='.')
    # plt.pause(0.001)
    plt.scatter(d4[:, 0][0], d4[:, 1][0],
                color=colors[scid], marker='o', s=300)  # 起点
    plt.scatter(d4[:, 0][-1], d4[:, 1][-1],
                color=colors[5], marker='o', s=300)  # 起点


def mnx(edges, pos):
    gAnt = nx.Graph()  # 创建：空的 无向图
    gAnt.add_weighted_edges_from(edges)  # 向图中添加多条赋权边: (node1,node2,weight)
    # print(edges)
    # nx.draw(gAnt, pos, with_labels=False,node_size=5)  # , alpha=0.8
    # plt.show()
    # print("图加载完成")
    '''start = time.time()

    # labels = nx.get_edge_attributes(gAnt, 'weight')
    # nx.draw_networkx_edge_labels(
    #     gAnt, pos, edge_labels=labels, font_color='c')  # 显示权值
    # nx.draw_networkx_nodes(gAnt, pos, nodelist=[
    #                        0, 17], node_color='yellow')  # 设置顶点颜色
    # nx.draw_networkx_nodes(gAnt, pos, nodelist=[
    #                        7, 12], node_color='lime')  # 设置顶点颜色
    # nx.draw_networkx_edges(gAnt, pos, edgelist=[(
    #     2, 4), (13, 14)], edge_color='lime', width=2.5)  # 设置边的颜色
    # nx.draw_networkx_edges(gAnt, pos, edgelist=[(
    #     11, 12)], edge_color='r', width=2.5)  # 设置边的颜色


    gAnt.remove_edge(13, 14)  # 删除边 (13,17)
 
    # 4. 限制条件：多个必经点 (N7,N15)
    # 解决方案：遍历从起点到终点的简单路径，求满足必经点条件的最短路径
    # minWPath4 = min([path  # 返回 key 为最小值的 path
    #                  # gAnt 中所有起点为0、终点为17的简单路径
    #                  for path in nx.all_simple_paths(gAnt, 0, 15000)
    #                  if all(n in path for n in (17, 28))],  # 满足路径中包括顶点 N7,N15
    #                 key=lambda x: sum(gAnt.edges[edge]['weight'] for edge in nx.utils.pairwise(x)))  # key 为加权路径长度
    # lenPath = sum(gAnt.edges[edge]['weight']
    #               for edge in nx.utils.pairwise(minWPath4))  # 求指定路径的加权路径长度
    # print("\n问题4: 多个必经点的约束")
    # print("S 到 E 的最短加权路径: ", minWPath4)
    # print("S 到 E 的最短加权路径长度: ", lenPath)

    # plt.show()
    end = time.time()
    print(f'{end-start:5.8f} s')'''
    return gAnt


def view_maps(view):

    points = []
    out_edges = []
    with open("D:/session/map/RoadLine.json", 'rb') as load_f:
        RoadLine = json.load(load_f)
    point_cnt = 0
    for line_id, rd in enumerate(RoadLine):  # len(RoadLine)):
        dt = rd["geometry"]["coordinates"]
        if dt == []:
            continue

        index_zero = point_cnt
        # npdt=np.array(dt)
        points += dt

        # print(index_zero)
        for id in range(len(dt)-1):
            node_id1 = id+index_zero
            val_dis = fun.GetDistance(points[node_id1], points[node_id1+1])
            if(val_dis != -1):
                out_edges.append((node_id1, node_id1+1, val_dis))
                continue
            out_edges.append((node_id1, node_id1+1, 0))
            # print(node_id1,node_id1+1,points[node_id1],points[node_id1+1]) #,dt[node_id1],npdt[node_id1+1],val_dis)
            # del points[node_id1+1]

        point_cnt += len(dt)
        # break
    # print(point_cnt)
    # print(points)
    # print(cnt)
    with open("D:/session/map/RoadPoint.json", 'rb') as load_f:
        RoadPoint = json.load(load_f)
    np_points = np.array(points)

    # print(RoadPoint)
    # print(vasum)
    # print(np_points[0],np_points[1],fun.GetDistance(np_points[0],np_points[1]))

    for rd in RoadPoint:  # len(RoadLine)):
        dt = rd["geometry"]["coordinates"]
        for p2_index, p2 in enumerate(points):
            val_dis = fun.GetDistance222(dt, p2)
            valll = dt-np_points
            if(val_dis < (1e-4)):
                print(val_dis, p2_index, rd["properties"]
                      ["osm_id"], rd["properties"]["osm_id_2"])

            # break

    #     if dt == []:
    #         continue
    #     for id,val in dt:

    #     if view:
    #         dtarray = np.array(dt)
    #         plt.scatter(dtarray[1], dtarray[0],
    #                     color=colors[0], edgecolors='none', s=10, linewidth=0.50)
    return points


def GET_MIN_index(roadLines, point, rd, roadpoint):

    idx1 = rd["properties"]["osm_id"]
    idx2 = rd["properties"]["osm_id_2"]
    mps1_ids, _pxy1 = roadLines[idx1]
    mps2_ids, _pxy2 = roadLines[idx2]

    su = np.sum(np.fabs(np.array(_pxy1)-point), axis=1)
    amin = np.min(su)
    # if(amin!=0):
    #     # print(amin)
    #     return
    m1_id = np.where(su == amin)
    # print(m1_id[0][0],idx2)
    su = np.sum(np.fabs(np.array(_pxy2)-point), axis=1)
    m2_id = np.where(su == np.min(su))

    # print(dasd[0][0],mps2_ids)

    # if mps2_ids[m2_id[0][0]]==15112:
    #     print("aaaaaaaaa",mps2_ids[m2_id[0][0]],mps1_ids[m1_id[0][0]])
    # if(mps1_ids[m1_id[0][0]] < mps2_ids[m2_id[0][0]]):
    roadpoint.append([mps1_ids[m1_id[0][0]], mps2_ids[m2_id[0][0]]])
    # mps2_ids[m2_id[0][0]] = mps1_ids[m1_id[0][0]]

    # else:
    # roadpoint.append([mps2_ids[m2_id[0][0]], mps1_ids[m1_id[0][0]]])
    # mps1_ids[m1_id[0][0]] = mps2_ids[m2_id[0][0]]
    return m1_id[0][0], m2_id[0][0], mps1_ids[m1_id[0][0]], mps2_ids[m2_id[0][0]]


def view_maps2(view):
    points = []
    roadLines = dict()
    with open("D:/session/map/RoadLine.json", 'rb') as load_f:
        RoadLine = json.load(load_f)
    point_cnt = 0
    for line_id, rd in enumerate(RoadLine):  # len(RoadLine)):
        dt = rd["geometry"]["coordinates"]
        road_id = rd["properties"]["osm_id"]
        edgelis = []
        if dt == []:
            continue
        index_zero = point_cnt

        points += dt
        if view:
            DTS = np.array(dt)
            plt.plot(DTS[:, 0], DTS[:, 1], color=colors[2], linewidth=0.50)

        for id in range(len(dt)):
            node_id1 = id+index_zero

            edgelis.append(node_id1)

        point_cnt += len(dt)
        if not road_id in roadLines:
            if index_zero == 7667:
                print("dt", edgelis, index_zero)
            roadLines.setdefault(road_id, (edgelis, dt))
        else:

            lival, _dt = roadLines[road_id]
            roadLines[road_id] = (
                lival.copy()+edgelis.copy(), _dt.copy()+dt.copy())
            # roadLines.setdefault(road_id, (lival+edgelis.copy(), _dt+dt))
            # if index_zero==7667:
            # print("dt",lival+edgelis,road_id,lival)
            # print(roadLines[386])

    # print(roadLines[386])
    with open("D:/session/map/RoadPoint.json", 'rb') as pload_f:
        RoadPoint = json.load(pload_f)
    roadpoint = []
    for i, rd in enumerate(RoadPoint):  # len(RoadLine)):
        point = rd["geometry"]["coordinates"]
        ret = GET_MIN_index(roadLines, point, rd, roadpoint)
        if point == []:
            print("point == [] 151")
            continue
        if view:
            dtarray = np.array(point)
            plt.scatter(dtarray[0], dtarray[1],
                        color=colors[3], edgecolors='none', s=100, linewidth=0.50)
    return points, roadLines, roadpoint


def perdata(roadLines, points):
    out_edges = []
    intlen = 0
    for key, (imd, _pnodes) in roadLines.items():
        # print(imd)
        for id in range(len(imd)-1):
            valdis = fun.GetDistance(points[imd[id]], points[imd[id+1]])
            if(valdis != -1):
                out_edges.append((imd[id], imd[id+1], valdis))
                continue
            out_edges.append((imd[id], imd[id+1], 0.001))
            # print((imd[id], imd[id+1], valdis),points[imd[id]],points[imd[id+1]])

        # intlen+=len(imd)
    dictpoints = dict()

    for id, (_long, _lan) in enumerate(points):
        dictpoints.setdefault(id, (_long, _lan))
    return out_edges, dictpoints


def calrandmpath(gant, source, target):
    paths = nx.single_source_shortest_path(gant, source)
    print("len:", len(paths))
    return paths
# gAnt=mnx(out_edges, dictpoints)
# calrandmpath(gAnt,0,15000)


def calrandmpath_1(gant, source, target):
    paths = nx.single_source_shortest_path(gant, source)
    print("len:", len(paths))
    return paths


def fix_people_id(points, rescue_peoples, roadpoint):
    poeple_info = []
    nppoints = np.array(points)
    # print(rescue_peoples[0])
    for id, (point, people_id, type) in enumerate(rescue_peoples):
        ret = np.fabs(nppoints-point)
        su = np.sum(ret, axis=1)
        m1_id = np.where(su == np.min(su))
        for p1, p2 in roadpoint:
            if p2 == m1_id[0][0]:
                m1_id[0][0] = p1
        # print(ret)
        # print(ret[m1_id[0][0]],nppoints[m1_id[0][0]],point)
        poeple_info.append((point, people_id, type, m1_id[0][0]))
    # print(poeple_info[0])

    return poeple_info


def cal_path_weight_people(path, poeple_info):
    p_num = 0
    t_num = 0
    for id, (point, people_id, type, point_id) in enumerate(poeple_info):
        if point_id in path:
            p_num += 1
            t_num += type
    # if t_num>42:
    print("人数:", p_num, "分数:", t_num)
    return t_num


def path_2_csv(path, p2, p3, strname):
    f = open(strname, 'w', encoding='utf-8', newline='')
    csv_writer = csv.writer(f)
    csv_writer.writerow(path)
    csv_writer.writerow(p2)
    csv_writer.writerow(p3)
    f.close()


def path_2_pdm(points, path, p2, p3, strname):
    _lpoints = [[], [], [], [], [], []]
    for val in path:
        _lpoints[0].append(points[val])
    for val in p2:
        _lpoints[1].append(points[val])
    for val in p3:
        _lpoints[2].append(points[val])
    _lpoints[3] = copy.deepcopy(_lpoints[0])
    _lpoints[4] = copy.deepcopy(_lpoints[1])
    _lpoints[5] = copy.deepcopy(_lpoints[2])
    _lpoints[0].extend(_lpoints[3])
    _lpoints[1].extend(_lpoints[4])
    _lpoints[2].extend(_lpoints[5])
    alldata = _lpoints[0]+_lpoints[1]+_lpoints[2]
    data1 = pd.DataFrame(alldata, columns=['longitude', 'latitude'])
    return data1


def deledge(gant, path):
    for i in range(len(path)-1):
        gant.remove_edge(path[i], path[i+1])  # 删除边 (13,17)


def trf_id(points, pltlins, poeple_info):
    ret = []
    new_path_node = copy.deepcopy(pltlins)

    for _id, val in enumerate(pltlins[0]):
        new_path_node[0][_id] = poeple_info[val-1][3]
        # print(val,"       ",poeple_info[val-1],new_path_node[0][_id])
    for _id, val in enumerate(pltlins[1]):
        new_path_node[1][_id] = poeple_info[val-1][3]
    for _id, val in enumerate(pltlins[2]):
        new_path_node[2][_id] = poeple_info[val-1][3]
    #             break
    # for _id,val in enumerate(pltlins[1]):
    #     for id, (point, people_id, type, point_id) in enumerate(poeple_info):
    #         if people_id == val:
    #             new_path_node[1][id]=point_id
    #             break
    # for _id,val in enumerate(pltlins[2]):
    #     for id, (point, people_id, type, point_id) in enumerate(poeple_info):
    #         if people_id == val:
    #             new_path_node[2][id]=point_id
    #             break
    return new_path_node


def gen_points_paths(gant, passpoints):
    # print("经过点:", passpoints)
    gant_del_start = gant.copy()
    gant_del_start.remove_node(passpoints[0])
    for i in range(len(passpoints) - 1, -1, -1):
        if not passpoints[i] in gant_del_start:
            print("del:", passpoints[i])
            del passpoints[i]

    while(True):
        flist = 0
        for i in range(len(passpoints) - 1, -1, -1):
            val = nx.algorithms.shortest_paths.generic.has_path(
                gant_del_start, passpoints[i-1], passpoints[i])
            if(val == False):
                del passpoints[i]
                flist += 1
        if flist > 0:
            mbool = False
        else:
            break
        # print(flist)
    # print(passpoints)

    path = nx.astar_path(gant_del_start, passpoints[0], passpoints[1])
    # print("s:",path)
    for i in range(1, len(passpoints)-2):
        try:
            _pp = nx.astar_path(gant_del_start, passpoints[i], passpoints[i+1])
            path += _pp
        except:
            print("ERROR356 s:", passpoints[0:3], passpoints[i],
                  passpoints[i+1], i, len(passpoints)-2)
    _path = nx.astar_path(gant, passpoints[i+1], passpoints[0])
    path += _path
    # print("e:",_path)

    return path
# def id_filter(new_path_node):


def red_step_1path():
    path = './data/gen_people_75id.csv'
    read_csv = csv.reader(open(path, 'r'), dialect='excel')

    _ldd = 0
    pltlins = []
    for line in read_csv:  # 循环输出csv中的所有数据
        pltlins.append(list(int(val) for val in line))
    # print(pltlins)#行人ID
    return pltlins


def red_step_1path_pandas(sd0):
    pltlins = []
    for i in range(3):
        val = sd0[i]['people_id'].values.astype("int")
        pltlins.append(list(val))

    return pltlins


def _main_fun(sdo0, round_id):
    points, roadLines, roadpoint = view_maps2(False)  # 读取地图
    out_edges, dictpoints = perdata(roadLines, points)  # 修正数据
    rescue_peoples = fun.read_client_path_new(round_id)  # 读取行人数据
    poeple_info = fix_people_id(points, rescue_peoples, roadpoint)
    gant = nx.Graph()  # 创建：空的 无向图
    gant.add_weighted_edges_from(out_edges)  # 向图中添加多条赋权边: (node1,node2,weight)

    # print(points)
    out_edges = []
    for x, y in roadpoint:
        # print(x,y)
        if(points[x] == points[y]):
            out_edges.append((x, y, 0.000))
            continue
        valdis = fun.GetDistance(points[x], points[y])
        # if(valdis==-1):
        #     out_edges.append((x, y, 0.000))
        if(valdis < 7):
            out_edges.append((x, y, valdis))
            continue
        # print(valdis,points[x], points[y])
        # if(valdis != -1):
        #     # out_edges.append((x, y, valdis))
        #     continue
        # out_edges.append((x, y, 0.000))
        # if(valdis!=-1) and valdis<10:
        #     out_edges.append((x, y, 0.000))
            # print(valdis)
        # print("a")
    gant.add_weighted_edges_from(out_edges)  # 向图中添加多条赋权边: (node1,node2,weight)
    # nx.draw(gant, dictpoints, with_labels=False,node_size=5)  # , alpha=0.8
    print(nx.astar_path(gant, 0, 500))
    # print(roadpoint)
    # for id, (point, people_id, type, point_id) in enumerate(poeple_info):
    #     if not point_id in gant:
    #         print(point_id)
    pltlins = red_step_1path_pandas(sdo0)  # 行人ID
    new_path_node = trf_id(points, pltlins, poeple_info)
    #
    path1 = [[], [], []]
    data = []
    for i in range(3):
        s1 = new_path_node[i][0:35]
        s1 += [new_path_node[i][0]]
        s2 = [new_path_node[i][0]]
        s2 += new_path_node[i][35:80]
        s2 += [new_path_node[i][0]]
        s3 = [new_path_node[i][0]]
        s3 += new_path_node[i][80:]
        s3 += [new_path_node[i][0]]
        path1[0] = gen_points_paths(gant, s1)
        path1[1] = gen_points_paths(gant, s2)
        path1[2] = gen_points_paths(gant, s3)
        ret = cal_path_weight_people(path1[0], poeple_info)
        ret = cal_path_weight_people(path1[1], poeple_info)
        ret = cal_path_weight_people(path1[2], poeple_info)
        data.append(path_2_pdm(
            points, path1[0], path1[1], path1[2], './data/gen_people_1.json'))
    stringname = 'D:/session/session_2/subject_2/team_path_' + \
        str(round_id)+'.json'
    fun.toJons((data[0], data[1], data[2]), stringname, round_id)
    # # print(path1[0])
    # plt.figure(1)
    # vm.show_path_by_id(path1[0],1,0)
    # vm.show_path_by_id(path1[1],2,0)
    # vm.show_path_by_id(path1[2],3,0)

    # plt.show()


if __name__ == '__main__':
    # plt.figure(dpi=90,figsize=(24,8))

    # plt.rcParams['savefig.dpi'] = 300 #图片像素
    # plt.rcParams['figure.dpi'] = 300 #分辨率
    points, roadLines, roadpoint = view_maps2(False)  # 读取地图
    out_edges, dictpoints = perdata(roadLines, points)  # 修正数据
    gant = nx.Graph()  # 创建：空的 无向图
    gant.add_weighted_edges_from(out_edges)  # 向图中添加多条赋权边: (node1,node2,weight)

    # print(points)
    out_edges = []
    for x, y in roadpoint:
        # print(x,y)
        if(points[x] == points[y]):
            out_edges.append((x, y, 0.000))
            continue
        valdis = fun.GetDistance(points[x], points[y])
        # if(valdis==-1):
        #     out_edges.append((x, y, 0.000))
        if(valdis < 7):
            out_edges.append((x, y, valdis))
            continue

    gant.add_weighted_edges_from(out_edges)  # 向图中添加多条赋权边: (node1,node2,weight)
    # nx.draw(gant, dictpoints, with_labels=False,node_size=5)  # , alpha=0.8
    Paths = [[3239, 3252, 3251, 3250, 3249, 3248, 3247, 3246, 3245, 3244, 917, 916, 915, 914, 913, 912, 911, 910, 909, 908, 907, 906, 905, 904, 903, 902, 901, 900, 899, 773, 772, 771, 770, 769, 768, 767, 799, 798, 797, 796, 795, 794, 793, 792, 791, 790, 789, 788, 787, 786, 785, 784, 707, 708, 709, 710, 981, 980, 979, 978, 977, 976, 975, 974, 973, 972, 971, 970, 969,
              968, 967, 966, 965, 964, 963, 962, 961, 960, 2827, 2826, 2825, 2824, 2823, 4448, 4447, 4446, 4445, 4444, 4443, 4442, 4441, 2799, 2798, 2797, 2796, 2795, 2794, 2793, 2792, 2791, 2790, 2789, 2788, 2787, 2786, 2785, 2784, 2783, 2782, 2781, 2780, 2779, 2778, 2777, 2776, 2775, 2774, 2773, 2772, 2771, 2770, 2769, 2768, 2767, 2766, 2765, 2764, 2763, 2762, 2761, 2760, 2681, 2682, 1238, 1239, 1240, 1241, 1242, 1243, 3072, 3073, 3074, 3075, 3076, 3077, 1948, 1947, 2691, 2692, 2351, 2352, 2353, 2354, 2355, 2356, 2357, 2358, 2359, 2350, 2349, 2348, 2347, 2346, 2345, 2344, 2343, 1880, 1879, 1878, 3389, 3388, 3387, 3386, 3385, 3384, 3383, 3382, 3381, 3380, 3374, 3375, 3376, 3377, 3378, 3379, 2899, 2898, 2897, 1907, 1906, 1905, 1904, 1903, 3143, 3142, 3141, 3140, 1186, 1185, 1184, 1183, 1182, 1181, 1180, 1179, 1941, 1942, 2881, 2880, 2881, 1942, 1943, 1944, 1945, 1893, 1894, 1895, 1896, 1897, 1898, 1899, 1900, 3272, 3271, 3270, 3269, 3268, 3267, 2329, 2328, 2327, 2355, 2356, 2357, 2358, 2359, 2360, 2359, 2358, 2357, 2356, 2355, 2354, 2353, 2352, 2351, 2692, 2691, 1947, 1948, 1949, 1950, 1951, 1952, 1953, 1954, 1955, 1956, 4515, 4516, 3237, 3238, 3239, 3240]]
    Paths.append([3241, 3242, 517, 516, 2731, 516, 515, 514, 513, 512, 391, 390, 391, 512, 513, 512, 391, 390, 389, 388, 387, 386, 385, 384, 916, 915, 914, 913, 912, 911, 910, 909, 908, 907, 906, 905, 904, 903, 902, 901, 900, 899, 773, 772, 771, 770, 769, 768, 767, 799, 800, 801, 802, 803, 804, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814, 815, 816, 817, 507, 817, 816, 815, 814, 813, 812, 811, 810, 809, 808, 807, 806, 805, 804, 803, 802, 801, 800, 799, 767, 768, 769, 770, 771, 772, 773, 899, 898, 897, 896, 895, 894, 893, 892, 891, 890, 889,
                  888, 887, 886, 885, 884, 883, 882, 881, 880, 879, 878, 877, 876, 875, 874, 873, 940, 939, 938, 937, 936, 4245, 4244, 4253, 4252, 4251, 4250, 4251, 4231, 4230, 4229, 4228, 4227, 4226, 4225, 4224, 4223, 4222, 4221, 4220, 4219, 4218, 2567, 2568, 876, 877, 878, 879, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 3244, 3245, 3246, 3247, 3248, 3249, 3250, 3251, 3252, 3239, 3240])
    Paths.append([3239, 3238, 3237, 4516, 4515, 1956, 1955, 1954, 1953, 1952, 1951, 1950, 1949, 1948, 1947, 1946, 203, 202, 1902, 1901, 1900, 1899, 1898, 1897, 1896, 1892, 1891, 1890, 1889, 1888, 3300, 3301, 3302, 3303, 3304, 3305, 3306, 3307, 3308, 3309, 3310, 3311, 3312, 3313, 3314, 3315, 3316, 3317, 3318, 3319, 3320, 3321, 3359, 3360, 3361, 3362, 3363, 3364, 1920, 1919, 1918, 1917, 1918, 1919, 1920, 3364, 3363, 3362, 3361, 3360, 3359, 3321, 3320,
                  3319, 3318, 3317, 3316, 3315, 3314, 3313, 3312, 3311, 3310, 3309, 3308, 3307, 3306, 3305, 3304, 3303, 3302, 3301, 3300, 1888, 1889, 1890, 1891, 1892, 1896, 1897, 1898, 1899, 1900, 1901, 1902, 202, 203, 1946, 1947, 1948, 1949, 1950, 1951, 1952, 1953, 1954, 1955, 1956, 1957, 1958, 1959, 1960, 1961, 1962, 1963, 1964, 1965, 1966, 1967, 1968, 1969, 1970, 1971, 1972, 1973, 1974, 1975, 1976, 1977, 1978, 1979, 3646, 3645, 3644, 3643, 3642, 3641])

    Paths.append([2522, 2521, 2520, 2519, 2518, 2517, 2516, 2515, 2514, 2513, 2512, 1392, 1391, 1390, 4556, 4555, 4554, 4553, 4552, 4551, 4550, 4566, 4565, 4564, 4563, 4562, 4561, 4560, 3528, 3527, 3526, 3525, 3524, 3523, 4713, 4714, 4715, 3488, 3487, 3486, 3485, 3484, 3483, 3482, 3481, 3480, 3479, 3062, 3063, 3064,
                  3065, 3066, 3067, 2724, 2723, 2722, 2721, 2720, 2719, 2718, 2717, 2716, 2715, 2714, 2715, 2716, 2717, 2718, 395, 394, 209, 208, 207, 206, 205, 204, 1123, 1122, 1121, 1120, 1119, 4908, 4909, 1372, 1373, 1643, 1644, 1645, 1646, 5152, 5151, 5150, 5149, 5148, 5147, 5146, 5145, 5144, 5143, 5142, 2521, 2522, 4656])
    Paths.append([2522, 2521, 2520, 2519, 2518, 2517, 2516, 2515, 2514, 2513, 2512, 1392, 1393, 1394, 3449, 3448, 1096, 1095, 1094, 1093, 1530, 1529, 1537, 1536, 1535, 1534, 1533, 106, 105, 104,
                  103, 102, 101, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 5382, 5381, 5380, 5379, 5378, 5377, 5376, 5367, 5366, 5349, 5350, 5358, 5359, 5360, 2264, 2263, 2262, 2261, 2260, 2259, 2258, 2257, 2256, 2255, 2254, 2253, 2252, 1525, 1524, 4885, 4886, 4626, 4627, 4628, 3501, 3502, 3503, 4722, 4721, 4720, 297, 296, 295, 294, 4631, 4632, 4633, 4634, 4635, 4636, 4637, 4638, 4639, 4640, 4641, 4642, 4643, 4644, 4645, 4646, 4647, 1097, 1098, 1099, 2511, 2512, 2513, 2514, 2515, 2516, 2517, 2518, 2519, 2520, 2521, 2522, 4656])
    Paths.append([2522, 2523, 2524, 1621, 1622, 1623, 2501, 2502, 2501, 2500, 2499, 269, 270, 2046, 2047, 4661, 4662, 4663, 4662, 4661, 4660, 4659, 4658, 4657, 4656])
    
    # Paths.append()
    # show_path_by_id(Paths[0], 0, 1)
    # show_path_by_id(Paths[1], 1, 2)

    # Paths = [[980, 979, 978, 977, 976, 975, 974, 973, 972, 971, 970, 969, 968, 967, 966, 965, 964, 963, 962, 961, 960, 960, 2827, 2826, 2825, 2824, 2823, 4448, 4447, 4446, 4446, 4445, 4444, 4443, 4442, 4441, 2799, 2798, 2797, 2796, 2795, 2794, 2793, 2792, 2791, 2790, 2789, 2788, 2788, 2787, 2786, 2785, 2784, 2783, 2782, 2781, 2780, 2779, 2778, 2777, 2776, 2775, 2774, 2773, 2772, 2771, 2770, 2769, 2768, 2767, 2766, 2765, 2764, 2763, 2762, 2761, 2760, 2681, 2682, 1238, 1239, 1240, 1241, 1242, 1243, 3072, 3073, 3074, 3075, 3076, 3077, 1948, 1947, 2691, 2692, 2351, 2352, 2353, 2354, 2355, 2356, 2357, 2358, 2359, 2350, 2349, 2348, 2347, 2346, 2345, 2344, 2343, 1880, 1879, 1878, 3389, 3388, 3387, 3386, 3385, 3384, 3383, 3382, 3381, 3380, 3374, 3375, 3376, 3377, 3378, 3379, 2899, 2898,
    #           2897, 1907, 1906, 1905, 1904, 1903, 1903, 3143, 3142, 3141, 3140, 1186, 1185, 1184, 1183, 1182, 1181, 1180, 1179, 1941, 1942, 2881, 2880, 2880, 2881, 1942, 1943, 1944, 1945, 1893, 1894, 1895, 1896, 1897, 1898, 1899, 1900, 3272, 3271, 3270, 3269, 3268, 3267, 2329, 2328, 2327, 2355, 2356, 2357, 2358, 2359, 2360, 2360, 2359, 2358, 2357, 2356, 2355, 2354, 2353, 2352, 2351, 2692, 2691, 1947, 1948, 1949, 1950, 1951, 1952, 1953, 1954, 1955, 1956, 4515, 4516, 3237, 3238, 3239, 3240, 3240, 3239, 3252, 3251, 3250, 3249, 3248, 3247, 3246, 3245, 3244, 917, 916, 915, 914, 913, 912, 911, 910, 909, 908, 907, 906, 905, 904, 903, 902, 901, 900, 899, 773, 772, 771, 770, 769, 768, 767, 799, 798, 797, 796, 795, 794, 793, 792, 791, 790, 789, 788, 787, 786, 785, 784, 707, 708, 709, 710, 981, 980]]
    ''' path=nx.astar_path(gant,3240,980) #0 500
    show_path_by_id(path,0,1)
    Paths+=path[1:].copy()
    path=nx.astar_path(gant,980,960) #0 500
    show_path_by_id(path,0,1)
    Paths+=path[1:].copy()
    path=nx.astar_path(gant,960,4446) #0 500
    show_path_by_id(path,0,1)
    Paths+=path[1:].copy()
    path=nx.astar_path(gant,4446,2788) #0 500
    show_path_by_id(path,0,1)
    Paths+=path[1:].copy()
    path=nx.astar_path(gant,2788,1903) #0 500
    show_path_by_id(path,0,1)
    Paths+=path[1:].copy()
    path=nx.astar_path(gant,1903,2880) #0 500
    show_path_by_id(path,0,1)
    Paths+=path[1:].copy()
    path=nx.astar_path(gant,2880,2360) #0 500
    show_path_by_id(path,0,1)
    Paths+=path[1:].copy()
    path=nx.astar_path(gant,2360,3240) #0 500
    show_path_by_id(path,0,1)
    Paths+=path[1:].copy()


    path = nx.astar_path(gant, 980, 960)  # 0 500
    show_path_by_id(path, 0, 1)
    Paths += path
    path = nx.astar_path(gant, 960, 4446)  # 0 500
    show_path_by_id(path, 0, 1)
    Paths += path
    path = nx.astar_path(gant, 4446, 2788)  # 0 500
    show_path_by_id(path, 0, 1)
    Paths += path
    path = nx.astar_path(gant, 2788, 1903)  # 0 500
    show_path_by_id(path, 0, 1)
    Paths += path
    path = nx.astar_path(gant, 1903, 2880)  # 0 500
    show_path_by_id(path, 0, 1)
    Paths += path
    path = nx.astar_path(gant, 2880, 2360)  # 0 500
    show_path_by_id(path, 0, 1)
    Paths += path
    path = nx.astar_path(gant, 2360, 3240)  # 0 500
    show_path_by_id(path, 0, 1)
    Paths += path
    path = nx.astar_path(gant, 3240, 980)  # 0 500
    show_path_by_id(path, 0, 1)
    Paths += path'''

    # path=nx.astar_path(gant,2788,1903) #0 500
    # show_path_by_id(path,0,1)
    # Paths+=path

    print(Paths)
    nx.draw(gant, dictpoints, with_labels=True, node_size=5,
            font_size=10, font_color="r")  # , alpha=0.8
    plt.show()
